"""800"""
"""
RGB 颜色 "#AABBCC" 可以简写成 "#ABC" 。

例如，"#15c" 其实是 "#1155cc" 的简写。
现在，假如我们分别定义两个颜色 "#ABCDEF" 和 "#UVWXYZ"，则他们的相似度可以通过这个表达式 -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2 来计算。

那么给你一个按 "#ABCDEF" 形式定义的字符串 color 表示 RGB 颜色，请你以字符串形式，返回一个与它相似度最大且可以简写的颜色。（比如，可以表示成类似 "#XYZ" 的形式）

任何 具有相同的（最大）相似度的答案都会被视为正确答案。
"""
"""
示例 1：
    输入：color = "#09f166"
    输出："#11ee66"
解释： 
    因为相似度计算得出 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73
    这已经是所有可以简写的颜色中最相似的了

示例 2：
    输入：color = "#4e3fe1"
    输出："#5544dd"
 

提示：
    color.length == 7
    color[0] == '#'
    对于任何 i > 0，color[i] 都是一个在范围 ['0', 'f'] 内的 16 进制数
"""


def similarRGB(color: str) -> str:
    """方法一：枚举
    由于从 #000 到 #fff 一共只有 16^3 = 4096 种颜色，因此我们可以枚举这些颜色，并计算其与 color 的相似度。

    在枚举所有的颜色时，我们可以使用三重循环，每一重循环的范围为 0 到 15。
    设三重循环分别为 R，G 和 B，那么其对应的颜色的十六进制值为 17 * R * (1 << 16) + 17 * G * (1 << 8) + 17 * B，
    这里的 17 由 0x11 = 16 + 1 = 17 得来，(1 << 16) 和 (1 << 8) 分别为 R 和 G 的左移位数。

    在计算两种颜色的相似度时，我们从其十六进制值可以得到三种颜色对应的值，
    即 r = (hex >> 16) % 256，g = (hex >> 8) % 256 以及 b = hex % 256。
    随后通过 (r1 - r2)^2 + (g1 - g2)^2 + (b1 - b2)^2 计算相似度。

    在枚举完所有的颜色后，我们需要将答案转换为 16 进制输出，此时可以用 Java 或 Python 中的 format，
    用 06x 表示输出为 6 位的十六进制数（x 表示十六进制），且少于 6 位的高位补 0。
    :param color:
    :return:
    """

    def similarRGB(hex1, hex2):
        r1, g1, b1 = hex1 >> 16, (hex1 >> 8) % 256, hex1 % 256
        r2, g2, b2 = hex2 >> 16, (hex2 >> 8) % 256, hex2 % 256
        return -(r1 - r2) ** 2 - (g1 - g2) ** 2 - (b1 - b2) ** 2

    hex1 = int(color[1:], 16)
    ans = 0
    for r in range(16):
        for g in range(16):
            for b in range(16):
                hex2 = 17 * r * (1 << 16) + 17 * g * (1 << 8) + 17 * b
                if similarRGB(hex1, hex2) > similarRGB(hex1, ans):
                    ans = hex2
    print("#{:06x}".format(ans))
    return "#{:06x}".format(ans)


def similarRGB_v2(color: str) -> str:
    """方法二：独立性 + 枚举
    我们可以发现，颜色中的每一维都是独立的，
    因此我们只需要分别计算出 color = #ABCDEF 中与 AB，CD 和 EF 相似度最大的颜色即可。最终的答案为这三个颜色的结合。

    对于 AB，我们要在 00 到 ff 中找到一个相似度最大的。
    在方法一中我们得知，00 到 ff 均为 17 的倍数，因此我们需要找到一个 17 的倍数，使得其与 AB 的差的绝对值最小。
    显然，当 AB mod 17 > 8 时，取刚好比 AB 大的那个数；当 AB mod 17 <= 8 时，取刚好比 AB 小或与 AB 相等的那个数。
    :param color:
    :return:
    """

    def f(comp):
        q, r = divmod(int(comp, 16), 17)
        if r > 8:
            q += 1
        return '{:02x}'.format(17 * q)

    return '#' + f(color[1:3]) + f(color[3:5]) + f(color[5:])


if __name__ == '__main__':
    similarRGB("#4e3fe1")
